/**********************************************************

@description:
*File Name:preThreadTree.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sat 26 Apr 2025 10:47:28 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode{
	char data;
	struct tnode* lchild;
	struct tnode* rchild;
	unsigned char ltag:1;//0->lchild, 1->pre 
	unsigned char rtag:1;//0->rchild, 1->next
}tnode;
void createTree1(tnode **n,char*data,int* idx){
	char ch;
	ch=data[*idx];
	*idx+=1;
	if(ch == '#'){
		*n=NULL;		
	}else{
		*n=(tnode*)malloc(sizeof(tnode));
		(*n)->data=ch;
		(*n)->ltag=0;
		(*n)->rtag=0;
		createTree1(&(*n)->lchild,data,idx);
		createTree1(&(*n)->rchild,data,idx);
	}
}
void preThread(tnode *t,tnode **pre){
	if(t){
		//dosomething
		if(!t->lchild){
			t->ltag=1;
			t->lchild=*pre;
		}
		if(*pre && !(*pre)->rchild){
			(*pre)->rtag=1;
			(*pre)->rchild=t;
		}
		*pre=t;
		//in the previous code,*pre=NULL and valued to t->lchild, an segmentation core fault will happen
		if(!t->ltag)
			preThread(t->lchild,pre);
		preThread(t->rchild,pre);
	}
}
typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%c ",n->data);
}
tnode* getFirst(tnode *t){
	return t;
}
tnode * getNext(tnode* node){
	if(node->rtag)
		return node->rchild;
	else
		return node->lchild;
}
void preThreadTraverse(tnode* t,visit v){
	tnode* cur=getFirst(t);
	while(cur){
		v(cur);
		cur=getNext(cur);
	}
}

int main(int argc,char **argv){
	tnode* t=NULL;
	tnode* pre=NULL;
	int index=0;
	createTree1(&t,argv[1],&index);
	preThread(t,&pre);
	pre->rtag=1;
	pre->rchild=NULL;
	preThreadTraverse(t,pn);
	printf("\n");
	return 0;
}
